home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / gnu / gawk / cawf2st.zoo / regexp.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-04-12  |  38.7 KB  |  1,223 lines
  1. /*
  2.  * regcomp and regexec -- regsub and regerror are elsewhere
  3.  *
  4.  *      Copyright (c) 1986 by University of Toronto.
  5.  *      Written by Henry Spencer.  Not derived from licensed software.
  6.  *
  7.  *      Permission is granted to anyone to use this software for any
  8.  *      purpose on any computer system, and to redistribute it freely,
  9.  *      subject to the following restrictions:
  10.  *
  11.  *      1. The author is not responsible for the consequences of use of
  12.  *              this software, no matter how awful, even if they arise
  13.  *              from defects in it.
  14.  *
  15.  *      2. The origin of this software must not be misrepresented, either
  16.  *              by explicit claim or by omission.
  17.  *
  18.  *      3. Altered versions must be plainly marked as such, and must not
  19.  *              be misrepresented as being the original software.
  20.  *
  21.  * Beware that some of this code is subtly aware of the way operator
  22.  * precedence is structured in regular expressions.  Serious changes in
  23.  * regular-expression syntax might require a total rethink.
  24.  */
  25. #include <stdio.h>
  26. #ifdef  UNIX
  27. #ifdef  USG
  28. #include <string.h>
  29. #else
  30. #include <strings.h>
  31. #endif
  32. #else
  33. #include <string.h>
  34. #endif
  35. #include "regexp.h"
  36. #include "regmagic.h"
  37.  
  38. /*
  39.  * The "internal use only" fields in regexp.h are present to pass info from
  40.  * compile to execute that permits the execute phase to run lots faster on
  41.  * simple cases.  They are:
  42.  *
  43.  * regstart     char that must begin a match; '\0' if none obvious
  44.  * reganch      is the match anchored (at beginning-of-line only)?
  45.  * regmust      string (pointer into program) that match must include, or NULL
  46.  * regmlen      length of regmust string
  47.  *
  48.  * Regstart and reganch permit very fast decisions on suitable starting points
  49.  * for a match, cutting down the work a lot.  Regmust permits fast rejection
  50.  * of lines that cannot possibly match.  The regmust tests are costly enough
  51.  * that regcomp() supplies a regmust only if the r.e. contains something
  52.  * potentially expensive (at present, the only such thing detected is * or +
  53.  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
  54.  * supplied because the test in regexec() needs it and regcomp() is computing
  55.  * it anyway.
  56.  */
  57.  
  58. /*
  59.  * Structure for regexp "program".  This is essentially a linear encoding
  60.  * of a nondeterministic finite-state machine (aka syntax charts or
  61.  * "railroad normal form" in parsing technology).  Each node is an opcode
  62.  * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
  63.  * all nodes except BRANCH implement concatenation; a "next" pointer with
  64.  * a BRANCH on both ends of it is connecting two alternatives.  (Here we
  65.  * have one of the subtle syntax dependencies:  an individual BRANCH (as
  66.  * opposed to a collection of them) is never concatenated with anything
  67.  * because of operator precedence.)  The operand of some types of node is
  68.  * a literal string; for others, it is a node leading into a sub-FSM.  In
  69.  * particular, the operand of a BRANCH node is the first node of the branch.
  70.  * (NB this is *not* a tree structure:  the tail of the branch connects
  71.  * to the thing following the set of BRANCHes.)  The opcodes are:
  72.  */
  73.  
  74. /* definition   number  opnd?   meaning */
  75. #define END     0       /* no   End of program. */
  76. #define BOL     1       /* no   Match "" at beginning of line. */
  77. #define EOL     2       /* no   Match "" at end of line. */
  78. #define ANY     3       /* no   Match any one character. */
  79. #define ANYOF   4       /* str  Match any character in this string. */
  80. #define ANYBUT  5       /* str  Match any character not in this string. */
  81. #define BRANCH  6       /* node Match this alternative, or the next... */
  82. #define BACK    7       /* no   Match "", "next" ptr points backward. */
  83. #define EXACTLY 8       /* str  Match this string. */
  84. #define NOTHING 9       /* no   Match empty string. */
  85. #define STAR    10      /* node Match this (simple) thing 0 or more times. */
  86. #define PLUS    11      /* node Match this (simple) thing 1 or more times. */
  87. #define OPEN    20      /* no   Mark this point in input as start of #n. */
  88.                         /*      OPEN+1 is number 1, etc. */
  89. #define CLOSE   30      /* no   Analogous to OPEN. */
  90.  
  91. /*
  92.  * Opcode notes:
  93.  *
  94.  * BRANCH       The set of branches constituting a single choice are hooked
  95.  *              together with their "next" pointers, since precedence prevents
  96.  *              anything being concatenated to any individual branch.  The
  97.  *              "next" pointer of the last BRANCH in a choice points to the
  98.  *              thing following the whole choice.  This is also where the
  99.  *              final "next" pointer of each individual branch points; each
  100.  *              branch starts with the operand node of a BRANCH node.
  101.  *
  102.  * BACK         Normal "next" pointers all implicitly point forward; BACK
  103.  *              exists to make loop structures possible.
  104.  *
  105.  * STAR,PLUS    '?', and complex '*' and '+', are implemented as circular
  106.  *              BRANCH structures using BACK.  Simple cases (one character
  107.  *              per match) are implemented with STAR and PLUS for speed
  108.  *              and to minimize recursive plunges.
  109.  *
  110.  * OPEN,CLOSE   ...are numbered at compile time.
  111.  */
  112.  
  113. /*
  114.  * A node is one char of opcode followed by two chars of "next" pointer.
  115.  * "Next" pointers are stored as two 8-bit pieces, high order first.  The
  116.  * value is a positive offset from the opcode of the node containing it.
  117.  * An operand, if any, simply follows the node.  (Note that much of the
  118.  * code generation knows about this implicit relationship.)
  119.  *
  120.  * Using two bytes for the "next" pointer is vast overkill for most things,
  121.  * but allows patterns to get big without disasters.
  122.  */
  123. #define OP(p)   (*(p))
  124. #define NEXT(p) (((*((p)+1)&0377)<<8) + *((p)+2)&0377)
  125. #define OPERAND(p)      ((p) + 3)
  126.  
  127. /*
  128.  * See regmagic.h for one further detail of program structure.
  129.  */
  130.  
  131.  
  132. /*
  133.  * Utility definitions.
  134.  */
  135. #ifndef CHARBITS
  136. #define UCHARAT(p)      ((int)*(unsigned char *)(p))
  137. #else
  138. #define UCHARAT(p)      ((int)*(p)&CHARBITS)
  139. #endif
  140.  
  141. #define FAIL(m) { regerror(m); return(NULL); }
  142. #define ISMULT(c)       ((c) == '*' || (c) == '+' || (c) == '?')
  143. #define META    "^$.[()|?+*\\"
  144.  
  145. /*
  146.  * Flags to be passed up and down.
  147.  */
  148. #define HASWIDTH        01      /* Known never to match null string. */
  149. #define SIMPLE          02      /* Simple enough to be STAR/PLUS operand. */
  150. #define SPSTART         04      /* Starts with * or +. */
  151. #define WORST           0       /* Worst case. */
  152.  
  153. /*
  154.  * Global work variables for regcomp().
  155.  */
  156. static char *regparse;          /* Input-scan pointer. */
  157. static int regnpar;             /* () count. */
  158. static char regdummy;
  159. static char *regcode;           /* Code-emit pointer; ®dummy = don't. */
  160. static long regsize;            /* Code size. */
  161.  
  162. /*
  163.  * Forward declarations for regcomp()'s friends.
  164.  */
  165. #ifndef STATIC
  166. #define STATIC  static
  167. #endif
  168. STATIC char *reg();
  169. STATIC char *regbranch();
  170. STATIC char *regpiece();
  171. STATIC char *regatom();
  172. STATIC char *regnode();
  173. STATIC char *regnext();
  174. STATIC void regc();
  175. STATIC void reginsert();
  176. STATIC void regtail();
  177. STATIC void regoptail();
  178. #ifdef STRCSPN
  179. STATIC int strcspn();
  180. #endif
  181.  
  182. /*
  183.  - regcomp - compile a regular expression into internal code
  184.  *
  185.  * We can't allocate space until we know how big the compiled form will be,
  186.  * but we can't compile it (and thus know how big it is) until we've got a
  187.  * place to put the code.  So we cheat:  we compile it twice, once with code
  188.  * generation turned off and size counting turned on, and once "for real".
  189.  * This also means that we don't allocate space until we are sure that the
  190.  * thing really will compile successfully, and we never have to move the
  191.  * code and thus invalidate pointers into it.  (Note that it has to be in
  192.  * one piece because free() must be able to free it all.)
  193.  *
  194.  * Beware that the optimization-preparation code in here knows about some
  195.  * of the structure of the compiled regexp.
  196.  */
  197. regexp *
  198. regcomp(exp)
  199. char *exp;
  200. {
  201.         register regexp *r;
  202.         register char *scan;
  203.         register char *longest;
  204.         register int len;
  205.         int flags;
  206.         extern char *malloc();
  207.  
  208.         if (exp == NULL)
  209.                 FAIL("NULL argument");
  210.  
  211.         /* First pass: determine size, legality. */
  212.         regparse = exp;
  213.         regnpar = 1;
  214.         regsize = 0L;
  215.         regcode = ®dummy;
  216.         regc(MAGIC);
  217.         if (reg(0, &flags) == NULL)
  218.                 return(NULL);
  219.  
  220.         /* Small enough for pointer-storage convention? */
  221.         if (regsize >= 32767L)          /* Probably could be 65535L. */
  222.                 FAIL("regexp too big");
  223.  
  224.         /* Allocate space. */
  225.         r = (regexp *)malloc(sizeof(regexp) + (unsigned)regsize);
  226.         if (r == NULL)
  227.                 FAIL("out of space");
  228.  
  229.         /* Second pass: emit code. */
  230.         regparse = exp;
  231.         regnpar = 1;
  232.         regcode = r->program;
  233.         regc(MAGIC);
  234.         if (reg(0, &flags) == NULL)
  235.                 return(NULL);
  236.  
  237.         /* Dig out information for optimizations. */
  238.         r->regstart = '\0';     /* Worst-case defaults. */
  239.         r->reganch = 0;
  240.         r->regmust = NULL;
  241.         r->regmlen = 0;
  242.         scan = r->program+1;                    /* First BRANCH. */
  243.         if (OP(regnext(scan)) == END) {         /* Only one top-level choice. */
  244.                 scan = OPERAND(scan);
  245.  
  246.                 /* Starting-point info. */
  247.                 if (OP(scan) == EXACTLY)
  248.                         r->regstart = *OPERAND(scan);
  249.                 else if (OP(scan) == BOL)
  250.                         r->reganch++;
  251.  
  252.                 /*
  253.                  * If there's something expensive in the r.e., find the
  254.                  * longest literal string that must appear and make it the
  255.                  * regmust.  Resolve ties in favor of later strings, since
  256.                  * the regstart check works with the beginning of the r.e.
  257.                  * and avoiding duplication strengthens checking.  Not a
  258.                  * strong reason, but sufficient in the absence of others.
  259.                  */
  260.                 if (flags&SPSTART) {
  261.                         longest = NULL;
  262.                         len = 0;
  263.                         for (; scan != NULL; scan = regnext(scan))
  264.                                 if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= len) {
  265.                                         longest = OPERAND(scan);
  266.                                         len = strlen(OPERAND(scan));
  267.                                 }
  268.                         r->regmust = longest;
  269.                         r->regmlen = len;
  270.                 }
  271.         }
  272.  
  273.         return(r);
  274. }
  275.  
  276. /*
  277.  - reg - regular expression, i.e. main body or parenthesized thing
  278.  *
  279.  * Caller must absorb opening parenthesis.
  280.  *
  281.  * Combining parenthesis handling with the base level of regular expression
  282.  * is a trifle forced, but the need to tie the tails of the branches to what
  283.  * follows makes it hard to avoid.
  284.  */
  285. static char *
  286. reg(paren, flagp)
  287. int paren;                      /* Parenthesized? */
  288. int *flagp;
  289. {
  290.         register char *ret;
  291.         register char *br;
  292.         register char *ender;
  293.         register int parno;
  294.         int flags;
  295.  
  296.         *flagp = HASWIDTH;      /* Tentatively. */
  297.  
  298.         /* Make an OPEN node, if parenthesized. */
  299.         if (paren) {
  300.                 if (regnpar >= NSUBEXP)
  301.                         FAIL("too many ()");
  302.                 parno = regnpar;
  303.                 regnpar++;
  304.                 ret = regnode(OPEN+parno);
  305.         } else
  306.                 ret = NULL;
  307.  
  308.         /* Pick up the branches, linking them together. */
  309.         br = regbranch(&flags);
  310.         if (br == NULL)
  311.                 return(NULL);
  312.         if (ret != NULL)
  313.                 regtail(ret, br);       /* OPEN -> first. */
  314.         else
  315.                 ret = br;
  316.         if (!(flags&HASWIDTH))
  317.                 *flagp &= ~HASWIDTH;
  318.         *flagp |= flags&SPSTART;
  319.         while (*regparse == '|') {
  320.                 regparse++;
  321.                 br = regbranch(&flags);
  322.                 if (br == NULL)
  323.                         return(NULL);
  324.                 regtail(ret, br);       /* BRANCH -> BRANCH. */
  325.                 if (!(flags&HASWIDTH))
  326.                         *flagp &= ~HASWIDTH;
  327.                 *flagp |= flags&SPSTART;
  328.         }
  329.  
  330.         /* Make a closing node, and hook it on the end. */
  331.         ender = regnode((paren) ? CLOSE+parno : END);   
  332.         regtail(ret, ender);
  333.  
  334.         /* Hook the tails of the branches to the closing node. */
  335.         for (br = ret; br != NULL; br = regnext(br))
  336.                 regoptail(br, ender);
  337.  
  338.         /* Check for proper termination. */
  339.         if (paren && *regparse++ != ')') {
  340.                 FAIL("unmatched ()");
  341.         } else if (!paren && *regparse != '\0') {
  342.                 if (*regparse == ')') {
  343.                         FAIL("unmatched ()");
  344.                 } else
  345.                         FAIL("junk on end");    /* "Can't happen". */
  346.                 /* NOTREACHED */
  347.         }
  348.  
  349.         return(ret);
  350. }
  351.  
  352. /*
  353.  - regbranch - one alternative of an | operator
  354.  *
  355.  * Implements the concatenation operator.
  356.  */
  357. static char *
  358. regbranch(flagp)
  359. int *flagp;
  360. {
  361.         register char *ret;
  362.         register char *chain;
  363.         register char *latest;
  364.         int flags;
  365.  
  366.         *flagp = WORST;         /* Tentatively. */
  367.  
  368.         ret = regnode(BRANCH);
  369.         chain = NULL;
  370.         while (*regparse != '\0' && *regparse != '|' && *regparse != ')') {
  371.                 latest = regpiece(&flags);
  372.                 if (latest == NULL)
  373.                         return(NULL);
  374.                 *flagp |= flags&HASWIDTH;
  375.                 if (chain == NULL)      /* First piece. */
  376.                         *flagp |= flags&SPSTART;
  377.                 else
  378.                         regtail(chain, latest);
  379.                 chain = latest;
  380.         }
  381.         if (chain == NULL)      /* Loop ran zero times. */
  382.                 (void) regnode(NOTHING);
  383.  
  384.         return(ret);
  385. }
  386.  
  387. /*
  388.  - regpiece - something followed by possible [*+?]
  389.  *
  390.  * Note that the branching code sequences used for ? and the general cases
  391.  * of * and + are somewhat optimized:  they use the same NOTHING node as
  392.  * both the endmarker for their branch list and the body of the last branch.
  393.  * It might seem that this node could be dispensed with entirely, but the
  394.  * endmarker role is not redundant.
  395.  */
  396. static char *
  397. regpiece(flagp)
  398. int *flagp;
  399. {
  400.         register char *ret;
  401.         register char op;
  402.         register char *next;
  403.         int flags;
  404.  
  405.         ret = regatom(&flags);
  406.         if (ret == NULL)
  407.                 return(NULL);
  408.  
  409.         op = *regparse;
  410.         if (!ISMULT(op)) {
  411.                 *flagp = flags;
  412.                 return(ret);
  413.         }
  414.  
  415.         if (!(flags&HASWIDTH) && op != '?')
  416.                 FAIL("*+ operand could be empty");
  417.         *flagp = (op != '+') ? (WORST|SPSTART) : (WORST|HASWIDTH);
  418.  
  419.         if (op == '*' && (flags&SIMPLE))
  420.                 reginsert(STAR, ret);
  421.         else if (op == '*') {
  422.                 /* Emit x* as (x&|), where & means "self". */
  423.                 reginsert(BRANCH, ret);                 /* Either x */
  424.                 regoptail(ret, regnode(BACK));          /* and loop */
  425.                 regoptail(ret, ret);                    /* back */
  426.                 regtail(ret, regnode(BRANCH));          /* or */
  427.                 regtail(ret, regnode(NOTHING));         /* null. */
  428.         } else if (op == '+' && (flags&SIMPLE))
  429.                 reginsert(PLUS, ret);
  430.         else if (op == '+') {
  431.                 /* Emit x+ as x(&|), where & means "self". */
  432.                 next = regnode(BRANCH);                 /* Either */
  433.                 regtail(ret, next);
  434.                 regtail(regnode(BACK), ret);            /* loop back */
  435.                 regtail(next, regnode(BRANCH));         /* or */
  436.                 regtail(ret, regnode(NOTHING));         /* null. */
  437.         } else if (op == '?') {
  438.                 /* Emit x? as (x|) */
  439.                 reginsert(BRANCH, ret);                 /* Either x */
  440.                 regtail(ret, regnode(BRANCH));          /* or */
  441.                 next = regnode(NOTHING);                /* null. */
  442.                 regtail(ret, next);
  443.                 regoptail(ret, next);
  444.         }
  445.         regparse++;
  446.         if (ISMULT(*regparse))
  447.                 FAIL("nested *?+");
  448.  
  449.         return(ret);
  450. }
  451.  
  452. /*
  453.  - regatom - the lowest level
  454.  *
  455.  * Optimization:  gobbles an entire sequence of ordinary characters so that
  456.  * it can turn them into a single node, which is smaller to store and
  457.  * faster to run.  Backslashed characters are exceptions, each becoming a
  458.  * separate node; the code is simpler that way and it's not worth fixing.
  459.  */
  460. static char *
  461. regatom(flagp)
  462. int *flagp;
  463. {
  464.         register char *ret;
  465.         int flags;
  466.  
  467.         *flagp = WORST;         /* Tentatively. */
  468.  
  469.         switch (*regparse++) {
  470.         case '^':
  471.                 ret = regnode(BOL);
  472.                 break;
  473.         case '$':
  474.                 ret = regnode(EOL);
  475.                 break;
  476.         case '.':
  477.                 ret = regnode(ANY);
  478.                 *flagp |= HASWIDTH|SIMPLE;
  479.                 break;
  480.         case '[': {
  481.                         register int class;
  482.                         register int classend;
  483.  
  484.                         if (*regparse == '^') { /* Complement of range. */
  485.                                 ret = regnode(ANYBUT);
  486.                                 regparse++;
  487.                         } else
  488.                                 ret = regnode(ANYOF);
  489.                         if (*regparse == ']' || *regparse == '-')
  490.                                 regc(*regparse++);
  491.                         while (*regparse != '\0' && *regparse != ']') {
  492.                                 if (*regparse == '-') {
  493.                                         regparse++;
  494.                                         if (*regparse == ']' || *regparse == '\0')
  495.                                                 regc('-');
  496.                                         else {
  497.                                                 class = UCHARAT(regparse-2)+1;
  498.                                                 classend = UCHARAT(regparse);
  499.                                                 if (class > classend+1)
  500.                                                         FAIL("invalid [] range");
  501.                                                 for (; class <= classend; class++)
  502.                                                         regc(class);
  503.                                                 regparse++;
  504.                                         }
  505.                                 } else
  506.                                         regc(*regparse++);
  507.                         }
  508.                         regc('\0');
  509.                         if (*regparse != ']')
  510.                                 FAIL("unmatched []");
  511.                         regparse++;
  512.                         *flagp |= HASWIDTH|SIMPLE;
  513.                 }
  514.                 break;
  515.         case '(':
  516.                 ret = reg(1, &flags);
  517.                 if (ret == NULL)
  518.                         return(NULL);
  519.                 *flagp |= flags&(HASWIDTH|SPSTART);
  520.                 break;
  521.         case '\0':
  522.         case '|':
  523.         case ')':
  524.                 FAIL("internal urp");   /* Supposed to be caught earlier. */
  525.                 break;
  526.         case '?':
  527.         case '+':
  528.         case '*':
  529.                 FAIL("?+* follows nothing");
  530.                 break;
  531.         case '\\':
  532.                 if (*regparse == '\0')
  533.                         FAIL("trailing \\");
  534.                 ret = regnode(EXACTLY);
  535.                 regc(*regparse++);
  536.                 regc('\0');
  537.                 *flagp |= HASWIDTH|SIMPLE;
  538.                 break;
  539.         default: {
  540.                         register int len;
  541.                         register char ender;
  542.  
  543.                         regparse--;
  544.                         len = strcspn(regparse, META);
  545.                         if (len <= 0)
  546.                                 FAIL("internal disaster");
  547.                         ender = *(regparse+len);
  548.                         if (len > 1 && ISMULT(ender))
  549.                                 len--;          /* Back off clear of ?+* operand. */
  550.                         *flagp |= HASWIDTH;
  551.                         if (len == 1)
  552.                                 *flagp |= SIMPLE;
  553.                         ret = regnode(EXACTLY);
  554.                         while (len > 0) {
  555.                                 regc(*regparse++);
  556.                                 len--;
  557.                         }
  558.                         regc('\0');
  559.                 }
  560.                 break;
  561.         }
  562.  
  563.         return(ret);
  564. }
  565.  
  566. /*
  567.  - regnode - emit a node
  568.  */
  569. static char *                   /* Location. */
  570. regnode(op)
  571. char op;
  572. {
  573.         register char *ret;
  574.         register char *ptr;
  575.  
  576.         ret = regcode;
  577.         if (ret == ®dummy) {
  578.                 regsize += 3;
  579.                 return(ret);
  580.         }
  581.  
  582.         ptr = ret;
  583.         *ptr++ = op;
  584.         *ptr++ = '\0';          /* Null "next" pointer. */
  585.         *ptr++ = '\0';
  586.         regcode = ptr;
  587.  
  588.         return(ret);
  589. }
  590.  
  591. /*
  592.  - regc - emit (if appropriate) a byte of code
  593.  */
  594. static void
  595. regc(b)
  596. char b;
  597. {
  598.         if (regcode != ®dummy)
  599.                 *regcode++ = b;
  600.         else
  601.                 regsize++;
  602. }
  603.  
  604. /*
  605.  - reginsert - insert an operator in front of already-emitted operand
  606.  *
  607.  * Means relocating the operand.
  608.  */
  609. static void
  610. reginsert(op, opnd)
  611. char op;
  612. char *opnd;
  613. {
  614.         register char *src;
  615.         register char *dst;
  616.         register char *place;
  617.  
  618.         if (regcode == ®dummy) {
  619.                 regsize += 3;
  620.                 return;
  621.         }
  622.  
  623.         src = regcode;
  624.         regcode += 3;
  625.         dst = regcode;
  626.         while (src > opnd)
  627.                 *--dst = *--src;
  628.  
  629.         place = opnd;           /* Op node, where operand used to be. */
  630.         *place++ = op;
  631.         *place++ = '\0';
  632.         *place++ = '\0';
  633. }
  634.  
  635. /*
  636.  - regtail - set the next-pointer at the end of a node chain
  637.  */
  638. static void
  639. regtail(p, val)
  640. char *p;
  641. char *val;
  642. {
  643.         register char *scan;
  644.         register char *temp;
  645.         register int offset;
  646.  
  647.         if (p == ®dummy)
  648.                 return;
  649.  
  650.         /* Find last node. */
  651.         scan = p;
  652.         for (;;) {
  653.                 temp = regnext(scan);
  654.                 if (temp == NULL)
  655.                         break;
  656.                 scan = temp;
  657.         }
  658.  
  659.         if (OP(scan) == BACK)
  660.                 offset = scan - val;
  661.         else
  662.                 offset = val - scan;
  663.         *(scan+1) = (offset>>8)&0377;
  664.         *(scan+2) = offset&0377;
  665. }
  666.  
  667. /*
  668.  - regoptail - regtail on operand of first argument; nop if operandless
  669.  */
  670. static void
  671. regoptail(p, val)
  672. char *p;
  673. char *val;
  674. {
  675.         /* "Operandless" and "op != BRANCH" are synonymous in practice. */
  676.         if (p == NULL || p == ®dummy || OP(p) != BRANCH)
  677.                 return;
  678.         regtail(OPERAND(p), val);
  679. }
  680.  
  681. /*
  682.  * regexec and friends
  683.  */
  684.  
  685. /*
  686.  * Global work variables for regexec().
  687.  */
  688. static char *reginput;          /* String-input pointer. */
  689. static char *regbol;            /* Beginning of input, for ^ check. */
  690. static char **regstartp;        /* Pointer to startp array. */
  691. static char **regendp;          /* Ditto for endp. */
  692.  
  693. /*
  694.  * Forwards.
  695.  */
  696. STATIC int regtry();
  697. STATIC int regmatch();
  698. STATIC int regrepeat();
  699.  
  700. #ifdef DEBUG
  701. int regnarrate = 0;
  702. void regdump();
  703. STATIC char *regprop();
  704. #endif
  705.  
  706. /*
  707.  - regexec - match a regexp against a string
  708.  */
  709. int
  710. regexec(prog, string)
  711. register regexp *prog;
  712. register char *string;
  713. {
  714.         register char *s;
  715.         extern char *strchr();
  716.  
  717.         /* Be paranoid... */
  718.         if (prog == NULL || string == NULL) {
  719.                 regerror("NULL parameter");
  720.                 return(0);
  721.         }
  722.  
  723.         /* Check validity of program. */
  724.         if (UCHARAT(prog->program) != MAGIC) {
  725.                 regerror("corrupted program");
  726.                 return(0);
  727.         }
  728.  
  729.         /* If there is a "must appear" string, look for it. */
  730.         if (prog->regmust != NULL) {
  731.                 s = string;
  732.                 while ((s = strchr(s, prog->regmust[0])) != NULL) {
  733.                         if (strncmp(s, prog->regmust, prog->regmlen) == 0)
  734.                                 break;  /* Found it. */
  735.                         s++;
  736.                 }
  737.                 if (s == NULL)  /* Not present. */
  738.                         return(0);
  739.         }
  740.  
  741.         /* Mark beginning of line for ^ . */
  742.         regbol = string;
  743.  
  744.         /* Simplest case:  anchored match need be tried only once. */
  745.         if (prog->reganch)
  746.                 return(regtry(prog, string));
  747.  
  748.         /* Messy cases:  unanchored match. */
  749.         s = string;
  750.         if (prog->regstart != '\0')
  751.                 /* We know what char it must start with. */
  752.                 while ((s = strchr(s, prog->regstart)) != NULL) {
  753.                         if (regtry(prog, s))
  754.                                 return(1);
  755.                         s++;
  756.                 }
  757.         else
  758.                 /* We don't -- general case. */
  759.                 do {
  760.                         if (regtry(prog, s))
  761.                                 return(1);
  762.                 } while (*s++ != '\0');
  763.  
  764.         /* Failure. */
  765.         return(0);
  766. }
  767.  
  768. /*
  769.  - regtry - try match at specific point
  770.  */
  771. static int                      /* 0 failure, 1 success */
  772. regtry(prog, string)
  773. regexp *prog;
  774. char *string;
  775. {
  776.         register int i;
  777.         register char **sp;
  778.         register char **ep;
  779.  
  780.         reginput = string;
  781.         regstartp = prog->startp;
  782.         regendp = prog->endp;
  783.  
  784.         sp = prog->startp;
  785.         ep = prog->endp;
  786.         for (i = NSUBEXP; i > 0; i--) {
  787.                 *sp++ = NULL;
  788.                 *ep++ = NULL;
  789.         }
  790.         if (regmatch(prog->program + 1)) {
  791.                 prog->startp[0] = string;
  792.                 prog->endp[0] = reginput;
  793.                 return(1);
  794.         } else
  795.                 return(0);
  796. }
  797.  
  798. /*
  799.  - regmatch - main matching routine
  800.  *
  801.  * Conceptually the strategy is simple:  check to see whether the current
  802.  * node matches, call self recursively to see whether the rest matches,
  803.  * and then act accordingly.  In practice we make some effort to avoid
  804.  * recursion, in particular by going through "ordinary" nodes (that don't
  805.  * need to know whether the rest of the match failed) by a loop instead of
  806.  * by recursion.
  807.  */
  808. static int                      /* 0 failure, 1 success */
  809. regmatch(prog)
  810. char *prog;
  811. {
  812.         register char *scan;    /* Current node. */
  813.         char *next;             /* Next node. */
  814.         extern char *strchr();
  815.  
  816.         scan = prog;
  817. #ifdef DEBUG
  818.         if (scan != NULL && regnarrate)
  819.                 fprintf(stderr, "%s(\n", regprop(scan));
  820. #endif
  821.         while (scan != NULL) {
  822. #ifdef DEBUG
  823.                 if (regnarrate)
  824.                         fprintf(stderr, "%s...\n", regprop(scan));
  825. #endif
  826.                 next = regnext(scan);
  827.  
  828.                 switch (OP(scan)) {
  829.                 case BOL:
  830.                         if (reginput != regbol)
  831.                                 return(0);
  832.                         break;
  833.                 case EOL:
  834.                         if (*reginput != '\0')
  835.                                 return(0);
  836.                         break;
  837.                 case ANY:
  838.                         if (*reginput == '\0')
  839.                                 return(0);
  840.                         reginput++;
  841.                         break;
  842.                 case EXACTLY: {
  843.                                 register int len;
  844.                                 register char *opnd;
  845.  
  846.                                 opnd = OPERAND(scan);
  847.                                 /* Inline the first character, for speed. */
  848.                                 if (*opnd != *reginput)
  849.                                         return(0);
  850.                                 len = strlen(opnd);
  851.                                 if (len > 1 && strncmp(opnd, reginput, len) != 0)
  852.                                         return(0);
  853.                                 reginput += len;
  854.                         }
  855.                         break;
  856.                 case ANYOF:
  857.                         if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) == NULL)
  858.                                 return(0);
  859.                         reginput++;
  860.                         break;
  861.                 case ANYBUT:
  862.                         if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) != NULL)
  863.                                 return(0);
  864.                         reginput++;
  865.                         break;
  866.                 case NOTHING:
  867.                         break;
  868.                 case BACK:
  869.                         break;
  870.                 case OPEN+1:
  871.                 case OPEN+2:
  872.                 case OPEN+3:
  873.                 case OPEN+4:
  874.                 case OPEN+5:
  875.                 case OPEN+6:
  876.                 case OPEN+7:
  877.                 case OPEN+8:
  878.                 case OPEN+9: {
  879.                                 register int no;
  880.                                 register char *save;
  881.  
  882.                                 no = OP(scan) - OPEN;
  883.                                 save = reginput;
  884.  
  885.                                 if (regmatch(next)) {
  886.                                         /*
  887.                                          * Don't set startp if some later
  888.                                          * invocation of the same parentheses
  889.                                          * already has.
  890.                                          */
  891.                                         if (regstartp[no] == NULL)
  892.                                                 regstartp[no] = save;
  893.                                         return(1);
  894.                                 } else
  895.                                         return(0);
  896.                         }
  897.                         break;
  898.                 case CLOSE+1:
  899.                 case CLOSE+2:
  900.                 case CLOSE+3:
  901.                 case CLOSE+4:
  902.                 case CLOSE+5:
  903.                 case CLOSE+6:
  904.                 case CLOSE+7:
  905.                 case CLOSE+8:
  906.                 case CLOSE+9: {
  907.                                 register int no;
  908.                                 register char *save;
  909.  
  910.                                 no = OP(scan) - CLOSE;
  911.                                 save = reginput;
  912.  
  913.                                 if (regmatch(next)) {
  914.                                         /*
  915.                                          * Don't set endp if some later
  916.                                          * invocation of the same parentheses
  917.                                          * already has.
  918.                                          */
  919.                                         if (regendp[no] == NULL)
  920.                                                 regendp[no] = save;
  921.                                         return(1);
  922.                                 } else
  923.                                         return(0);
  924.                         }
  925.                         break;
  926.                 case BRANCH: {
  927.                                 register char *save;
  928.  
  929.                                 if (OP(next) != BRANCH)         /* No choice. */
  930.                                         next = OPERAND(scan);   /* Avoid recursion. */
  931.                                 else {
  932.                                         do {
  933.                                                 save = reginput;
  934.                                                 if (regmatch(OPERAND(scan)))
  935.                                                         return(1);
  936.                                                 reginput = save;
  937.                                                 scan = regnext(scan);
  938.                                         } while (scan != NULL && OP(scan) == BRANCH);
  939.                                         return(0);
  940.                                         /* NOTREACHED */
  941.                                 }
  942.                         }
  943.                         break;
  944.                 case STAR:
  945.                 case PLUS: {
  946.                                 register char nextch;
  947.                                 register int no;
  948.                                 register char *save;
  949.                                 register int min;
  950.  
  951.                                 /*
  952.                                  * Lookahead to avoid useless match attempts
  953.                                  * when we know what character comes next.
  954.                                  */
  955.                                 nextch = '\0';
  956.                                 if (OP(next) == EXACTLY)
  957.                                         nextch = *OPERAND(next);
  958.                                 min = (OP(scan) == STAR) ? 0 : 1;
  959.                                 save = reginput;
  960.                                 no = regrepeat(OPERAND(scan));
  961.                                 while (no >= min) {
  962.                                         /* If it could work, try it. */
  963.                                         if (nextch == '\0' || *reginput == nextch)
  964.                                                 if (regmatch(next))
  965.                                                         return(1);
  966.                                         /* Couldn't or didn't -- back up. */
  967.                                         no--;
  968.                                         reginput = save + no;
  969.                                 }
  970.                                 return(0);
  971.                         }
  972.                         break;
  973.                 case END:
  974.                         return(1);      /* Success! */
  975.                         break;
  976.                 default:
  977.                         regerror("memory corruption");
  978.                         return(0);
  979.                         break;
  980.                 }
  981.  
  982.                 scan = next;
  983.         }
  984.  
  985.         /*
  986.          * We get here only if there's trouble -- normally "case END" is
  987.          * the terminating point.
  988.          */
  989.         regerror("corrupted pointers");
  990.         return(0);
  991. }
  992.  
  993. /*
  994.  - regrepeat - repeatedly match something simple, report how many
  995.  */
  996. static int
  997. regrepeat(p)
  998. char *p;
  999. {
  1000.         register int count = 0;
  1001.         register char *scan;
  1002.         register char *opnd;
  1003.  
  1004.         scan = reginput;
  1005.         opnd = OPERAND(p);
  1006.         switch (OP(p)) {
  1007.         case ANY:
  1008.                 count = strlen(scan);
  1009.                 scan += count;
  1010.                 break;
  1011.         case EXACTLY:
  1012.                 while (*opnd == *scan) {
  1013.                         count++;
  1014.                         scan++;
  1015.                 }
  1016.                 break;
  1017.         case ANYOF:
  1018.                 while (*scan != '\0' && strchr(opnd, *scan) != NULL) {
  1019.                         count++;
  1020.                         scan++;
  1021.                 }
  1022.                 break;
  1023.         case ANYBUT:
  1024.                 while (*scan != '\0' && strchr(opnd, *scan) == NULL) {
  1025.                         count++;
  1026.                         scan++;
  1027.                 }
  1028.                 break;
  1029.         default:                /* Oh dear.  Called inappropriately. */
  1030.                 regerror("internal foulup");
  1031.                 count = 0;      /* Best compromise. */
  1032.                 break;
  1033.         }
  1034.         reginput = scan;
  1035.  
  1036.         return(count);
  1037. }
  1038.  
  1039. /*
  1040.  - regnext - dig the "next" pointer out of a node
  1041.  */
  1042. static char *
  1043. regnext(p)
  1044. register char *p;
  1045. {
  1046.         register int offset;
  1047.  
  1048.         if (p == ®dummy)
  1049.                 return(NULL);
  1050.  
  1051.         offset = NEXT(p);
  1052.         if (offset == 0)
  1053.                 return(NULL);
  1054.  
  1055.         if (OP(p) == BACK)
  1056.                 return(p-offset);
  1057.         else
  1058.                 return(p+offset);
  1059. }
  1060.  
  1061. #ifdef DEBUG
  1062.  
  1063. STATIC char *regprop();
  1064.  
  1065. /*
  1066.  - regdump - dump a regexp onto stdout in vaguely comprehensible form
  1067.  */
  1068. void
  1069. regdump(r)
  1070. regexp *r;
  1071. {
  1072.         register char *s;
  1073.         register char op = EXACTLY;     /* Arbitrary non-END op. */
  1074.         register char *next;
  1075.         extern char *strchr();
  1076.  
  1077.  
  1078.         s = r->program + 1;
  1079.         while (op != END) {     /* While that wasn't END last time... */
  1080.                 op = OP(s);
  1081.                 printf("%2d%s", s-r->program, regprop(s));      /* Where, what. */
  1082.                 next = regnext(s);
  1083.                 if (next == NULL)               /* Next ptr. */
  1084.                         printf("(0)");
  1085.                 else 
  1086.                         printf("(%d)", (s-r->program)+(next-s));
  1087.                 s += 3;
  1088.                 if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
  1089.                         /* Literal string, where present. */
  1090.                         while (*s != '\0') {
  1091.                                 putchar(*s);
  1092.                                 s++;
  1093.                         }
  1094.                         s++;
  1095.                 }
  1096.                 putchar('\n');
  1097.         }
  1098.  
  1099.         /* Header fields of interest. */
  1100.         if (r->regstart != '\0')
  1101.                 printf("start `%c' ", r->regstart);
  1102.         if (r->reganch)
  1103.                 printf("anchored ");
  1104.         if (r->regmust != NULL)
  1105.                 printf("must have \"%s\"", r->regmust);
  1106.         printf("\n");
  1107. }
  1108.  
  1109. /*
  1110.  - regprop - printable representation of opcode
  1111.  */
  1112. static char *
  1113. regprop(op)
  1114. char *op;
  1115. {
  1116.         register char *p;
  1117.         static char buf[50];
  1118.  
  1119.         (void) strcpy(buf, ":");
  1120.  
  1121.         switch (OP(op)) {
  1122.         case BOL:
  1123.                 p = "BOL";
  1124.                 break;
  1125.         case EOL:
  1126.                 p = "EOL";
  1127.                 break;
  1128.         case ANY:
  1129.                 p = "ANY";
  1130.                 break;
  1131.         case ANYOF:
  1132.                 p = "ANYOF";
  1133.                 break;
  1134.         case ANYBUT:
  1135.                 p = "ANYBUT";
  1136.                 break;
  1137.         case BRANCH:
  1138.                 p = "BRANCH";
  1139.                 break;
  1140.         case EXACTLY:
  1141.                 p = "EXACTLY";
  1142.                 break;
  1143.         case NOTHING:
  1144.                 p = "NOTHING";
  1145.                 break;
  1146.         case BACK:
  1147.                 p = "BACK";
  1148.                 break;
  1149.         case END:
  1150.                 p = "END";
  1151.                 break;
  1152.         case OPEN+1:
  1153.         case OPEN+2:
  1154.         case OPEN+3:
  1155.         case OPEN+4:
  1156.         case OPEN+5:
  1157.         case OPEN+6:
  1158.         case OPEN+7:
  1159.         case OPEN+8:
  1160.         case OPEN+9:
  1161.                 sprintf(buf+strlen(buf), "OPEN%d", OP(op)-OPEN);
  1162.                 p = NULL;
  1163.                 break;
  1164.         case CLOSE+1:
  1165.         case CLOSE+2:
  1166.         case CLOSE+3:
  1167.         case CLOSE+4:
  1168.         case CLOSE+5:
  1169.         case CLOSE+6:
  1170.         case CLOSE+7:
  1171.         case CLOSE+8:
  1172.         case CLOSE+9:
  1173.                 sprintf(buf+strlen(buf), "CLOSE%d", OP(op)-CLOSE);
  1174.                 p = NULL;
  1175.                 break;
  1176.         case STAR:
  1177.                 p = "STAR";
  1178.                 break;
  1179.         case PLUS:
  1180.                 p = "PLUS";
  1181.                 break;
  1182.         default:
  1183.                 regerror("corrupted opcode");
  1184.                 break;
  1185.         }
  1186.         if (p != NULL)
  1187.                 (void) strcat(buf, p);
  1188.         return(buf);
  1189. }
  1190. #endif
  1191.  
  1192. /*
  1193.  * The following is provided for those people who do not have strcspn() in
  1194.  * their C libraries.  They should get off their butts and do something
  1195.  * about it; at least one public-domain implementation of those (highly
  1196.  * useful) string routines has been published on Usenet.
  1197.  */
  1198. #ifdef STRCSPN
  1199. /*
  1200.  * strcspn - find length of initial segment of s1 consisting entirely
  1201.  * of characters not from s2
  1202.  */
  1203.  
  1204. static int
  1205. strcspn(s1, s2)
  1206. char *s1;
  1207. char *s2;
  1208. {
  1209.         register char *scan1;
  1210.         register char *scan2;
  1211.         register int count;
  1212.  
  1213.         count = 0;
  1214.         for (scan1 = s1; *scan1 != '\0'; scan1++) {
  1215.                 for (scan2 = s2; *scan2 != '\0';)       /* ++ moved down. */
  1216.                         if (*scan1 == *scan2++)
  1217.                                 return(count);
  1218.                 count++;
  1219.         }
  1220.         return(count);
  1221. }
  1222. #endif
  1223.